from collections import deque

from dataStructure.tree.binarySearchTree import BinarySearchTree


class DepthFirstSearch:
    """
    DepthFirstSearch represents a depth-first search algorithm for a binary search tree.
    """

    def __init__(self):
        self._stack = deque()

    def preorder_traversal(self, root):
        """
        Performs preorder traversal of the binary search tree.

        Args:
            root: Root node of the binary search tree.

        Returns:
            List: Nodes traversed in preorder order.
        """
        result = []
        self._preorder_traversal_helper(root, result)
        return result

    def _preorder_traversal_helper(self, node, result):
        if node is None:
            return

        result.append(node.data)
        self._preorder_traversal_helper(node.left, result)
        self._preorder_traversal_helper(node.right, result)

    def inorder_traversal(self, root):
        """
        Performs inorder traversal of the binary search tree.

        Args:
            root: Root node of the binary search tree.

        Returns:
            List: Nodes traversed in inorder order.
        """
        result = []
        self._inorder_traversal_helper(root, result)
        return result

    def _inorder_traversal_helper(self, node, result):
        if node is None:
            return

        self._inorder_traversal_helper(node.left, result)
        result.append(node.data)
        self._inorder_traversal_helper(node.right, result)

    def postorder_traversal(self, root):
        """
        Performs postorder traversal of the binary search tree.

        Args:
            root: Root node of the binary search tree.

        Returns:
            List: Nodes traversed in postorder order.
        """
        result = []
        self._postorder_traversal_helper(root, result)
        return result

    def _postorder_traversal_helper(self, node, result):
        if node is None:
            return

        self._postorder_traversal_helper(node.left, result)
        self._postorder_traversal_helper(node.right, result)
        result.append(node.data)

    def depth_limited_search(self, root, depth_limit):
        """
        Performs depth-limited search on the binary search tree.

        Args:
            root: Root node of the binary search tree.
            depth_limit: Maximum depth limit.

        Returns:
            List: Nodes traversed in depth-limited search order.
        """
        result = []
        self._depth_limited_search_helper(root, depth_limit, 0, result)
        return result

    def _depth_limited_search_helper(self, node, depth_limit, current_depth, result):
        if node is None or current_depth > depth_limit:
            return

        result.append(node.data)
        self._depth_limited_search_helper(node.left, depth_limit, current_depth + 1, result)
        self._depth_limited_search_helper(node.right, depth_limit, current_depth + 1, result)

    def iterative_deepening_search(self, root, max_depth):
        """
        Performs iterative deepening search on the binary search tree.

        Args:
            root: Root node of the binary search tree.
            max_depth: Maximum depth for iterative deepening search.

        Returns:
            List: Nodes traversed in iterative deepening search order.
        """
        result = []
        for depth_limit in range(max_depth + 1):
            self._depth_limited_search_helper(root, depth_limit, 0, result)
        return result

    def stack_depth_first_search(self, root):
        """
        Performs stack-based depth-first search on the binary search tree.

        Args:
            root: Root node of the binary search tree.

        Returns:
            List: Nodes traversed in stack-based depth-first search order.
        """
        result = []
        self._stack.append(root)

        while self._stack:
            node = self._stack.pop()
            result.append(node.data)

            if node.right:
                self._stack.append(node.right)
            if node.left:
                self._stack.append(node.left)

        return result

    def iterative_depth_first_search(self, root):
        """
        Performs iterative depth-first search on the binary search tree.

        Args:
            root: Root node of the binary search tree.

        Returns:
            List: Nodes traversed in iterative depth-first search order.
        """
        result = []
        if not root:
            return result

        stack = deque()
        stack.append(root)

        while stack:
            node = stack.pop()
            result.append(node.data)

            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)

        return result

if __name__ == "__main__":
    # Create a new binary search tree
    bst = BinarySearchTree()

    # Insert nodes into the binary search tree
    bst.insert(5)
    bst.insert(3)
    bst.insert(7)
    bst.insert(2)
    bst.insert(4)
    bst.insert(6)
    bst.insert(8)

    # 打印二叉搜索树
    print(bst)
    #            __________Node(5)__________
    #           /                           \
    #     ___Node(3)___               ___Node(7)___
    #    /             \             /             \
    # Node(2)       Node(4)       Node(6)       Node(8)

    # Create a DepthFirstSearch object
    dfs = DepthFirstSearch()

    # Perform preorder traversal
    preorder = dfs.preorder_traversal(bst.root)
    print("Preorder Traversal:", preorder)
    # Output: Preorder Traversal: [5, 3, 2, 4, 7, 6, 8]

    # Perform inorder traversal
    inorder = dfs.inorder_traversal(bst.root)
    print("Inorder Traversal:", inorder)
    # Output: Inorder Traversal: [2, 3, 4, 5, 6, 7, 8]

    # Perform postorder traversal
    postorder = dfs.postorder_traversal(bst.root)
    print("Postorder Traversal:", postorder)
    # Output: Postorder Traversal: [2, 4, 3, 6, 8, 7, 5]

    # Perform depth-limited search
    depth_limit = 2
    dls = dfs.depth_limited_search(bst.root, depth_limit)
    print(f"Depth-Limited Search (Depth Limit: {depth_limit}):", dls)
    # Output: Depth-Limited Search (Depth Limit: 2): [5, 3, 7]

    # Perform iterative deepening search
    max_depth = 3
    ids = dfs.iterative_deepening_search(bst.root, max_depth)
    print(f"Iterative Deepening Search (Max Depth: {max_depth}):", ids)
    # Output: Iterative Deepening Search (Max Depth: 3): [5, 3, 7, 2, 4, 6, 8]

    # Perform stack-based depth-first search
    stack_dfs = dfs.stack_depth_first_search(bst.root)
    print("Stack-Based Depth-First Search:", stack_dfs)
    # Output: Stack-Based Depth-First Search: [5, 3, 2, 4, 7, 6, 8]

    # Perform iterative depth-first search
    iterative_dfs = dfs.iterative_depth_first_search(bst.root)
    print("Iterative Depth-First Search:", iterative_dfs)
    # Output: Iterative Depth-First Search: [5, 3, 2, 4, 7, 6, 8]